package com.wx.algorithm.sort;

import java.util.Arrays;

/**
 * @desc: 排序集合
 * @author: wx
 * @time: 2019/12/12 5:38 PM
 */
public class SortCollection {

    public static void main(String args[]) {

        System.out.println("冒泡排序---------------");
        int[] bubblingArray = {5, 2, 1, 3, 7, 6, 4};
        bubblingSort(bubblingArray);
        System.out.println(Arrays.toString(bubblingArray));


        System.out.println("选择排序---------------");
        int[] selectArray = {4, 5, 6, 1, 2, 3};
        selectSort(selectArray);
        System.out.println(Arrays.toString(selectArray));

        System.out.println("插入排序---------------");
        int[] insertionArray = {4, 5, 6, 1, 2, 3};
        insertionSort(insertionArray);
        System.out.println(Arrays.toString(insertionArray));


        System.out.println("归并排序---------------");
        int[] mergeArray = {4, 5, 1, 6, 2, 3, 7, 10, 9, 8};
        mergeSortRun(mergeArray);
        System.out.println(Arrays.toString(mergeArray));

        System.out.println("归并计算左边最小值和---------------");
        int[] minArray = {4, 1, 3, 5, 0, 6};
        System.out.println("最小值总和:" + leftMinAdd(minArray));
        System.out.println(Arrays.toString(minArray));

        System.out.println("快排---------------");
        int[] fastArray = {3, 5, 4, 1, 6, 4};
        fastSort(fastArray, 0, fastArray.length - 1);
        System.out.println(Arrays.toString(fastArray));

        System.out.println("堆排---------------");
        int[] heapArray = {3, 1, 4, 7, 5, 8};
        heapSort(heapArray);
        System.out.println(Arrays.toString(heapArray));

        System.out.println("桶排序之计数排序---------------");
        int[] barrelArray = {4, 5, 1,1, 6,6,6,6 ,2, 3, 7, 10,10, 9,9, 8};
        barrelSort(barrelArray);
        System.out.println(Arrays.toString(barrelArray));

        System.out.println("桶排序之排序后相邻最大差值---------------");
        int[] barrelArrayTwo = {4, 5, 20, 6, 15, 9, 7, 19, 8, 7};
        System.out.println("最大值:"+barrelSortMax(barrelArrayTwo));

    }

    /**
     * 冒泡排序
     */
    static void bubblingSort(int[] array) {
        if (array == null) {
            return;
        }
        int n = array.length;
        if (n == 1) {
            return;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }


    /**
     * 选择排序--------------------------------------------------------------------------------
     */
    public static void selectSort(int[] array) {
        if (array == null) {
            return;
        }
        int n = array.length;
        if (n == 1) {
            return;
        }


        for (int i = 0; i < n; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }

            int temp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = temp;

        }

    }


    /**
     * 插入排序--------------------------------------------------------------------------------
     */
    public static void insertionSort(int[] array) {
        if (array == null) {
            return;
        }
        int n = array.length;
        if (n == 1) {
            return;
        }

        for (int i = 1; i < n; i++) {
            for (int j = i; j > 0 && array[j] < array[j - 1]; j--) {
                int temp = array[j];
                array[j] = array[j - 1];
                array[j - 1] = temp;
            }
        }
    }


    /**
     * 归并排序--------------------------------------------------------------------------------
     */
    public static void mergeSortRun(int[] array) {
        if (array == null) {
            return;
        }
        int n = array.length;
        if (n == 1) {
            return;
        }
        binary(array, 0, array.length - 1);
    }

    //二分
    private static void binary(int[] array, int start, int end) {
        if (start == end) {
            return;
        }
        //计算中间值
        int middle = start + ((end - start) / 2);
        binary(array, start, middle);
        binary(array, middle + 1, end);
        //外排合并
        merge(array, start, middle, end);
    }

    //外排合并
    private static void merge(int[] array, int start, int middle, int end) {
        int[] temp = new int[end - start + 1];
        int i = 0;
        int s = start;
        int m = middle + 1;
        while (s <= middle && m <= end) {
            if (array[s] < array[m]) {
                temp[i++] = array[s++];
            } else {
                temp[i++] = array[m++];
            }
        }

        while (s <= middle) {
            temp[i++] = array[s++];
        }

        while (m <= end) {
            temp[i++] = array[m++];
        }

        for (int j = 0; j < temp.length; j++) {
            array[start++] = temp[j];
        }

    }

    /**
     * 左边最小和累计--------------------------------------------------------------------------------
     */
    public static int leftMinAdd(int[] array) {
        if (array == null) {
            return 0;
        }
        int n = array.length;
        if (n == 1) {
            return array[0];
        }

        return binaryLeftMinAdd(array, 0, array.length - 1);
    }

    //二分左边最小和累计
    private static int binaryLeftMinAdd(int[] array, int start, int end) {
        if (start == end) {
            return 0;
        }
        //计算中间值
        int middle = start + ((end - start) / 2);
        return binaryLeftMinAdd(array, start, middle) + binaryLeftMinAdd(array, middle + 1, end) + mergeLeftMinAdd(array,
                start, middle, end);
    }

    //外排合并计数
    private static int mergeLeftMinAdd(int[] array, int start, int middle, int end) {
        int[] temp = new int[end - start + 1];
        int i = 0;
        int s = start;
        int m = middle + 1;
        int count = 0;
        while (s <= middle && m <= end) {
            if (array[s] < array[m]) {
                //累计总和
                count += array[s];
                temp[i++] = array[s++];
            } else {
                temp[i++] = array[m++];
            }
        }

        if (s <= middle) {
            //累计总和
            count += (middle - s) * count;
            while (s <= middle) {
                temp[i++] = array[s++];
            }
        }

        if (m <= end) {
            //累计总和
            count += (end - m) * count;
            while (m <= end) {
                temp[i++] = array[m++];
            }
        }

        for (int j = 0; j < temp.length; j++) {
            array[start++] = temp[j];
        }
        return count;
    }

    /**
     * 快排--------------------------------------------------------------------------------
     */
    public static void fastSort(int[] array, int start, int end) {

        if (start < end) {
            //随机数组下标,与最后下标交换
            int newEnd = start + (int) (Math.random() * (end - start + 1));
            int endValue = array[end];
            array[end] = array[newEnd];
            array[newEnd] = endValue;

            int[] partition = partition(array, start, end);

            fastSort(array, start, partition[0] - 1);
            fastSort(array, partition[1] + 1, end);
        }

    }

    //把数组切分为 <分区 ==分区 >分区，返回==分区
    private static int[] partition(int[] array, int start, int end) {
        //左边界
        int l = start - 1;
        //右边界
        int r = end;

        while (start < r) {
            if (array[start] < array[end]) {
                ++l;
                int value = array[start];
                array[start] = array[l];
                array[l] = value;
                start++;
            } else if (array[start] > array[end]) {
                --r;
                int value = array[start];
                array[start] = array[r];
                array[r] = value;
            } else {
                start++;
            }
        }

        if (r != end) {
            int value = array[end];
            array[end] = array[r];
            array[r] = value;
        }

        //返回相等的区间
        return new int[]{l + 1, r};
    }

    /**
     * 堆排序--------------------------------------------------------------------------------
     */
    public static void heapSort(int[] array) {
        if (array == null) {
            return;
        }
        int n = array.length;
        if (n == 1) {
            return;
        }

        //堆生成
        for (int i = 0; i < n; i++) {
            int index = i;
            while (array[index] > array[(index - 1) / 2]) {
                //交换值
                int max = array[index];
                array[index] = array[(index - 1) / 2];
                array[(index - 1) / 2] = max;
                //设置父节点
                index = (index - 1) / 2;
            }
        }


        while (n > 0){
            //记录父节点下标
            int fatherIndex = 0;
            //记录孩子节点的最大下标
            int maxIndex = 0;

            //最大值位置与逻辑最后位置交换
            n--;
            int maxValue = array[fatherIndex];
            array[fatherIndex] = array[n];
            array[n] = maxValue;


            while ((fatherIndex * 2) + 1 <  n){

                //计算左下标
                int leftIndex = (fatherIndex * 2) + 1;
                //计算右下标
                int rightIndex = leftIndex + 1;

                if (rightIndex >= n){
                    maxIndex = leftIndex;
                } else {
                    maxIndex = array[leftIndex] > array[rightIndex] ? leftIndex : rightIndex;
                }

                if (array[maxIndex] > array[fatherIndex]){
                    int temp = array[maxIndex];
                    array[maxIndex] = array[fatherIndex];
                    array[fatherIndex] = temp;
                    fatherIndex = maxIndex;
                } else {
                    break;
                }

            }

        }

    }

    /**
     * 桶排序-计数
     */
    public static void barrelSort(int[] array) {
        if (array == null) {
            return;
        }
        int n = array.length;
        if (n == 1) {
            return;
        }

        int max = 0;

        //遍历数组获取最大值
        for (int i = 0; i < array.length; i++) {
            max = Math.max(max,array[i]);
        }

        int[] temp = new int[max + 1];

        for (int i = 0; i < array.length; i++) {
            temp[array[i]]++;
        }

        int index = 0;
        for (int i = 0; i < temp.length; i++) {
            while (temp[i] -- > 0){
                array[index ++] = i ;
            }
        }

    }


    /**
     * 桶排序之排序后相邻最大差值
     */
    public static int barrelSortMax(int[] array) {
        if (array == null) {
            return 0;
        }
        int n = array.length;
        if (n == 1) {
            return 0;
        }

        int max = 0;
        int min = 0;

        //遍历数组获取最大值与最小值
        for (int i = 0; i < array.length; i++) {
            max = Math.max(max,array[i]);
            min = Math.min(min,array[i]);
        }

        //是否存储数据桶
        boolean[] arrayBoolean = new boolean[n + 1 ];
        //最大值桶
        int[] arrayMax = new int[n + 1 ];
        //最小值桶
        int[] arrayMin = new int[n + 1 ];



        for (int i = 0; i < array.length; i++) {
            //获取桶下标
            int barrelIndex = getBarrelIndex(array[i], max, min, n);
            //比较大小入桶
            arrayMax[barrelIndex] = arrayBoolean[barrelIndex] ? Math.max(arrayMax[barrelIndex],array[i]) : array[i];
            arrayMin[barrelIndex] = arrayBoolean[barrelIndex] ? Math.min(arrayMin[barrelIndex],array[i]) : array[i];
            arrayBoolean[barrelIndex] = true;
        }

        //差值
        int res = 0;
        int lastMax = arrayMax[0];

        for (int i = 1; i < arrayMin.length; i++){

            if (arrayBoolean[i]){
                res = Math.max(res,arrayMin[i] - lastMax);
                lastMax = arrayMax[i];

            }

        }

        return res;

    }

    //计算桶下标
    private static int  getBarrelIndex(int num,int max,int min,int length){
       return  (num - min) * length / (max - min);
    }

}
